package com.uam.core.entity.model.entity.uitls;

import java.security.MessageDigest;
import java.util.*;
import java.util.regex.Pattern;

/**
 * String类型工具类
 *
 * @author lishf
 */
public final class StringUtil {

	public static final String STRING_EMPTY = "";

	private static final String NULL = "null";

	private static final String U = "\\u";

	private static final int HASHMAP_INIT_SIZE = 32;

	public static final Pattern PUNCTUATION_REGEX = Pattern.compile("(?:\\p{P}|[\\s\\+\\$\\^<>=×￥~～`\\|])+", Pattern.MULTILINE);

	public static boolean isEmpty(String text) {
		if (text == null) {
			return true;
		}
		text = text.trim();
		return text.length() == 0 || text.equalsIgnoreCase(StringUtil.NULL);
	}

	public static String getNotNull(String text) {
		if (text == null || text.equalsIgnoreCase(StringUtil.NULL)) {
			return StringUtil.STRING_EMPTY;
		}
		return text.trim();
	}

	public static List<boolean[]> generateAllSplitCase(int count) {
		int i = 0;
		List<boolean[]> result = new ArrayList<boolean[]>();
		while (i < count) {
			List<boolean[]> splitCaseList = StringUtil.combination(++i, count);
			if (splitCaseList != null) {
				result.addAll(splitCaseList);
			}
		}
		return result;
	}

	public static List<boolean[]> combination(int pickCount, int count) {
		if (pickCount <= 0 || count <= 0) {
			return null;
		}
		if (pickCount > count) {
			pickCount = count;
		}
		List<boolean[]> result = new ArrayList<boolean[]>();
		if (pickCount == count) {
			int i = 0;
			boolean[] splitCase = new boolean[count];
			while (i < count) {
				splitCase[i++] = true;
			}
			result.add(splitCase);
			return result;
		}
		Stack<Integer> stack = new Stack<Integer>();
		StringUtil.combination(-1, pickCount, count, stack, result);
		stack.clear();
		stack = null;
		int size = result.size();
		if (size == 0) {
			return null;
		}
		return result;
	}

	public static void combination(int currIndexMax, int pickCount, int count, Stack<Integer> stack, List<boolean[]> result) {
		int size = stack.size();
		if (size == pickCount) {
			int i = 0;
			boolean[] splitCase = new boolean[count];
			while (i < size) {
				splitCase[stack.get(i++).intValue()] = true;
			}
			result.add(splitCase);
			return;
		}
		int i = currIndexMax + 1;
		while (i < count) {
			stack.push(Integer.valueOf(i));
			StringUtil.combination(i++, pickCount, count, stack, result);
			stack.pop();
		}
	}

	public static List<String[]> combination(String[] terms, int pickCount, int sizeMax) {
		if (terms == null || pickCount <= 0) {
			return null;
		}
		int count = terms.length;
		if (count == 0) {
			return null;
		}
		if (pickCount > count) {
			pickCount = count;
		}
		List<String[]> result = new  ArrayList<String[]>();
		if (pickCount == count) {
			result.add(terms);
			return result;
		}
		Stack<Integer> stack = new Stack<Integer>();
    	StringUtil.combination(-1, pickCount, count, stack, terms, sizeMax, result);
    	stack.clear();
    	stack = null;
    	int size = result.size();
    	if (size == 0) {
    		return null;
    	}
		return result;
	}

    public static void combination(int currIndexMax, int pickCount, int count, Stack<Integer> stack, String[] terms, int sizeMax, List<String[]> result) {
    	if (result.size() >= sizeMax) {
    		return;
    	}
    	int size = stack.size();
        if (size == pickCount) {
			int i = 0;
			String[] currTerms = new String[size];
			while (i < size) {
				currTerms[i] = terms[stack.get(i++).intValue()];
			}
			result.add(currTerms);
			return;
        }
        int i = currIndexMax + 1;
        while (i < count) {
            stack.push(Integer.valueOf(i));
            StringUtil.combination(i++, pickCount, count, stack, terms, sizeMax, result);
            stack.pop();
        }
    }

    public static String[] deleteRepetition(String[] src) {
    	if (src == null) {
    		return src;
    	}
    	int size = src.length;
    	if (size == 0) {
    		return src;
    	}
    	int i = 0;
    	Set<String> set = new HashSet<String>();
    	while (i < size) {
    		set.add(src[i++]);
    	}
    	return set.toArray(new String[set.size()]);
    }

	public static double similarity4Lcs(char[] src, char[] dest) {
		int i = 0;
		int destLength = dest.length;
		int srcLength = src.length;
		int[] tempVector = null;
		int[] lastVector = new int[srcLength + 1];
		int[] currVector = new int[srcLength + 1];
		while (i < destLength) {
			int j = 1;
			char character = dest[i++];
			while (j <= srcLength) {
				int k = j - 1;
				if (src[k] != character) {
					currVector[j] = Math.max(currVector[k], lastVector[j]);
				} else {
					currVector[j] = lastVector[k] + 1;
				}
				++j;
			}
			tempVector = lastVector;
			lastVector = currVector;
			currVector = tempVector;
		}
		tempVector = null;
		currVector = null;
		double mean = (srcLength + destLength) / 2.00D;
		return lastVector[srcLength] / mean;
	}

	public static double similarity4Lcs2(char[] src, char[] dest) {
		int i = 0;
		int subLength = 0;
		int srcLength = src.length;
		int destLength = dest.length;
		int[] vector = new int[destLength + 1];
		List<Integer> indexes = new ArrayList<Integer>();
		while (i < srcLength) {
			char c = src[i++];
			int j = destLength;
			while (j >= 1) {
				if (dest[--j] == c) {
					int currSubLength = vector[j] + 1;
					vector[j + 1] = currSubLength;
					if (subLength < currSubLength) {
						subLength = currSubLength;
						if (indexes.size() >= 1) {
							indexes.clear();
						}
						indexes.add(Integer.valueOf(i));
					} else if (subLength == currSubLength) {
						indexes.add(Integer.valueOf(i));
					}
				} else if (vector[j + 1] != 0) {
					vector[j + 1] = 0;
				}
			}
		}
		double mean = (srcLength + destLength) / 2.00D;
		return (indexes.size() * subLength) / mean;
	}

	public static double similarity4Levenshtein(char[] src, char[] dest) {
		int i = 0;
		int srcLength = src.length;
		int destLength = dest.length;
		int[] lastVector = new int[destLength + 1];
		while (i <= destLength) {
			lastVector[i] = i++;
		}
		i = 0;
		int[] currVector = new int[destLength + 1];
		while (i < srcLength) {
			char c = src[i++];
			currVector[0] = i;
			int j = 0;
			while (j < destLength) {
				if (dest[j++] == c) {
					currVector[j] = Math.min(Math.min(lastVector[j], currVector[j - 1]) + 1, lastVector[j - 1]);
				} else {
					currVector[j] = Math.min(Math.min(lastVector[j], currVector[j - 1]), lastVector[j - 1]) + 1;
				}
			}
			int[] tempVector = currVector;
			currVector = lastVector;
			lastVector = tempVector;
			tempVector = null;
		}
		double distance = lastVector[destLength];
		return 1.00D - distance / Math.max(srcLength, destLength);
	}

	private static int getSameCount(char[] src, char[] dest) {
		int count = 0;
		int i = 0;
		int srcLength = src.length;
		int destLength = dest.length;
		while (i < srcLength) {
			char c = src[i++];
			for (int j = 0; j < destLength; j++) {
				if (dest[j] == c) {
					++count;
					break;
				}
			}
		}
		return count;
	}

	public static double similarity4SameCount(char[] src, char[] dest) {
		double mean = (src.length + dest.length) / 2.00D;
		return Math.max(StringUtil.getSameCount(src, dest), StringUtil.getSameCount(dest, src)) / mean;
	}

	public static double similarity4Lcs(String[] src, String[] dest) {
		int i = 0;
		int destLength = dest.length;
		int srcLength = src.length;
		int[] tempVector = null;
		int[] lastVector = new int[srcLength + 1];
		int[] currVector = new int[srcLength + 1];
		while (i < destLength) {
			int j = 1;
			String term = dest[i++];
			while (j <= srcLength) {
				int k = j - 1;
				if (!src[k].equalsIgnoreCase(term)) {
					currVector[j] = Math.max(currVector[k], lastVector[j]);
				} else {
					currVector[j] = lastVector[k] + 1;
				}
				++j;
			}
			tempVector = lastVector;
			lastVector = currVector;
			currVector = tempVector;
		}
		tempVector = null;
		currVector = null;
		double mean = (srcLength + destLength) / 2.00D;
		return lastVector[srcLength] / mean;
	}

	public static double similarity4Lcs2(String[] src, String[] dest) {
		int i = 0;
		int subLength = 0;
		int srcLength = src.length;
		int destLength = dest.length;
		int[] vector = new int[destLength + 1];
		List<Integer> indexes = new ArrayList<Integer>();
		while (i < srcLength) {
			String term = src[i++];
			int j = destLength;
			while (j >= 1) {
				if (dest[--j].equalsIgnoreCase(term)) {
					int currSubLength = vector[j] + 1;
					vector[j + 1] = currSubLength;
					if (subLength < currSubLength) {
						subLength = currSubLength;
						if (indexes.size() >= 1) {
							indexes.clear();
						}
						indexes.add(Integer.valueOf(i));
					} else if (subLength == currSubLength) {
						indexes.add(Integer.valueOf(i));
					}
				} else if (vector[j + 1] != 0) {
					vector[j + 1] = 0;
				}
			}
		}
		double mean = (srcLength + destLength) / 2.00D;
		return (indexes.size() * subLength) / mean;
	}

	public static double similarity4Levenshtein(String[] src, String[] dest) {
		int i = 0;
		int srcLength = src.length;
		int destLength = dest.length;
		int[] lastVector = new int[destLength + 1];
		while (i <= destLength) {
			lastVector[i] = i++;
		}
		i = 0;
		int[] currVector = new int[destLength + 1];
		while (i < srcLength) {
			String term = src[i++];
			currVector[0] = i;
			int j = 0;
			while (j < destLength) {
				if (dest[j++].equalsIgnoreCase(term)) {
					currVector[j] = Math.min(Math.min(lastVector[j], currVector[j - 1]) + 1, lastVector[j - 1]);
				} else {
					currVector[j] = Math.min(Math.min(lastVector[j], currVector[j - 1]), lastVector[j - 1]) + 1;
				}
			}
			int[] tempVector = currVector;
			currVector = lastVector;
			lastVector = tempVector;
			tempVector = null;
		}
		double distance = lastVector[destLength];
		return 1.00D - distance / Math.max(srcLength, destLength);
	}

	private static int getSameCount(String[] src, String[] dest) {
		int count = 0;
		int i = 0;
		int srcLength = src.length;
		int destLength = dest.length;
		while (i < srcLength) {
			String term = src[i++];
			for (int j = 0; j < destLength; j++) {
				if (dest[j].equalsIgnoreCase(term)) {
					++count;
					break;
				}
			}
		}
		return count;
	}

	public static double similarity4SameCount(String[] src, String[] dest) {
		double mean = (src.length + dest.length) / 2.00D;
		return Math.max(StringUtil.getSameCount(src, dest), StringUtil.getSameCount(dest, src)) / mean;
	}

	public static int levenshtein(char[] src, char[] dest) {
		int i = 0;
		int srcLength = src.length;
		int destLength = dest.length;
		int[] lastVector = new int[destLength + 1];
		while (i <= destLength) {
			lastVector[i] = i++;
		}
		i = 0;
		int[] currVector = new int[destLength + 1];
		while (i < srcLength) {
			char c = src[i++];
			currVector[0] = i;
			int j = 0;
			while (j < destLength) {
				if (dest[j++] == c) {
					currVector[j] = Math.min(Math.min(lastVector[j], currVector[j - 1]) + 1, lastVector[j - 1]);
				} else {
					currVector[j] = Math.min(Math.min(lastVector[j], currVector[j - 1]), lastVector[j - 1]) + 1;
				}
			}
			int[] tempVector = currVector;
			currVector = lastVector;
			lastVector = tempVector;
			tempVector = null;
		}
		return lastVector[destLength];
	}

	public static int levenshtein(String[] src, String[] dest) {
		int i = 0;
		int srcLength = src.length;
		int destLength = dest.length;
		int[] lastVector = new int[destLength + 1];
		while (i <= destLength) {
			lastVector[i] = i++;
		}
		i = 0;
		int[] currVector = new int[destLength + 1];
		while (i < srcLength) {
			String term = src[i++];
			currVector[0] = i;
			int j = 0;
			while (j < destLength) {
				if (dest[j++].equalsIgnoreCase(term)) {
					currVector[j] = Math.min(Math.min(lastVector[j], currVector[j - 1]) + 1, lastVector[j - 1]);
				} else {
					currVector[j] = Math.min(Math.min(lastVector[j], currVector[j - 1]), lastVector[j - 1]) + 1;
				}
			}
			int[] tempVector = currVector;
			currVector = lastVector;
			lastVector = tempVector;
			tempVector = null;
		}
		return lastVector[destLength];
	}

	public static double ap(char[] target, char[] src) {
		int targetLength = target.length;
		int srcLength = src.length;
		int i = 0;
		Set<Character> targetSet = new HashSet<Character>();
		while (i < targetLength) {
			Character item = Character.valueOf(target[i++]);
			if (!targetSet.contains(item)) {
				targetSet.add(item);
			}
		}
		i = 0;
		double right = 0.00D;
		double score = 0.00D;
		if (srcLength >= targetLength) {
			while (i < targetLength) {
				if (targetSet.contains(Character.valueOf(src[i++]))) {
					right = right + 1.00D;
				}
				score = score + (right / i);
			}
		} else {
			while (i < srcLength) {
				if (targetSet.contains(Character.valueOf(src[i++]))) {
					right = right + 1.00D;
				}
				score = score + (right / i);
			}
			while (i < targetLength) {
				score = score + (right / ++i);
			}
		}
		return score / targetLength;
	}

	public static double map(char[][] target, char[][] src) {
		int targetLength = target.length;
		int srcLength = src.length;
		int i = 0;
		double totalScore = 0.00D;
		if (srcLength <= targetLength) {
			while (i < srcLength) {
				totalScore = totalScore + StringUtil.ap(target[i], src[i++]);
			}
		} else {
			while (i < targetLength) {
				totalScore = totalScore + StringUtil.ap(target[i], src[i++]);
			}
		}
		return totalScore / srcLength;
	}

	public static double rr(char target, char[] src) {
		int srcLength = src.length;
		int i = 0;
		while (i < srcLength) {
			if (src[i++] == target) {
				return 1.00D / Double.valueOf(i).doubleValue();
			}
		}
		return Float.MIN_NORMAL;
	}

	public static double mrr(char[] target, char[][] src) {
		int targetLength = target.length;
		int srcLength = src.length;
		int i = 0;
		double totalScore = 0.00D;
		if (srcLength <= targetLength) {
			while (i < srcLength) {
				totalScore = totalScore + StringUtil.rr(target[i], src[i++]);
			}
		} else {
			while (i < targetLength) {
				totalScore = totalScore + StringUtil.rr(target[i], src[i++]);
			}
		}
		return totalScore / srcLength;
	}

	public static double ap(String[] target, String[] src) {
		int targetLength = target.length;
		int srcLength = src.length;
		int i = 0;
		Set<String> targetSet = new HashSet<String>();
		while (i < targetLength) {
			String item = target[i++];
			if (!targetSet.contains(item)) {
				targetSet.add(item);
			}
		}
		i = 0;
		double right = 0.00D;
		double score = 0.00D;
		if (srcLength >= targetLength) {
			while (i < targetLength) {
				if (targetSet.contains(src[i++])) {
					right = right + 1.00D;
				}
				score = score + (right / i);
			}
		} else {
			while (i < srcLength) {
				if (targetSet.contains(src[i++])) {
					right = right + 1.00D;
				}
				score = score + (right / i);
			}
			while (i < targetLength) {
				score = score + (right / ++i);
			}
		}
		return score / targetLength;
	}

	public static double map(String[][] target, String[][] src) {
		int targetLength = target.length;
		int srcLength = src.length;
		int i = 0;
		double totalScore = 0.00D;
		if (srcLength <= targetLength) {
			while (i < srcLength) {
				totalScore = totalScore + StringUtil.ap(target[i], src[i++]);
			}
		} else {
			while (i < targetLength) {
				totalScore = totalScore + StringUtil.ap(target[i], src[i++]);
			}
		}
		return totalScore / srcLength;
	}

	public static double rr(String target, String[] src) {
		int srcLength = src.length;
		int i = 0;
		while (i < srcLength) {
			if (src[i++].equalsIgnoreCase(target)) {
				return 1.00D / Double.valueOf(i).doubleValue();
			}
		}
		return Float.MIN_NORMAL;
	}

	public static double mrr(String[] target, String[][] src) {
		int targetLength = target.length;
		int srcLength = src.length;
		int i = 0;
		double totalScore = 0.00D;
		if (srcLength <= targetLength) {
			while (i < srcLength) {
				totalScore = totalScore + StringUtil.rr(target[i], src[i++]);
			}
		} else {
			while (i < targetLength) {
				totalScore = totalScore + StringUtil.rr(target[i], src[i++]);
			}
		}
		return totalScore / srcLength;
	}

    public static boolean isChinese(char c) {
        return c >= 19968 && c <= 40869;
    }

    public static boolean isNumber(char c) {
        return c >= 48 && c <= 57;
    }

    public static boolean isAlphabet(char c) {
        return (c >= 97 && c <= 122) || (c >= 65 && c <= 90);
    }

    public static boolean isChinese(String text) {
        if (StringUtil.isEmpty(text)) {
            return false;
        }
        int i = 0;
        int length = text.length();
        while (i < length) {
            if(!StringUtil.isChinese(text.charAt(i++))) {
                return false;
            }
        }
        return true;
    }

	/**
	 * 按照指定精度，标准化数字
	 *
	 * @param numeric
	 *            待标准化的数字
	 * @param precision
	 *            数字的精度
	 * @return 转换结果
	 */
	public static String numeric4Standard(String numeric, int precision) {
		if (StringUtil.isEmpty(numeric)) {
			return "";
		}
		StringBuilder strNumeric = new StringBuilder(numeric);
		int index = strNumeric.indexOf(".");
		if (index == -1) {
			strNumeric.append(".");
			for (int i = 0; i < precision; i++) {
				strNumeric.append("0");
			}
			return strNumeric.toString();
		} else {
			int currLen = strNumeric.length();
			int currPrec = currLen - index;
			int distance = precision - currPrec + 1;
			if (distance == 0) {
				return strNumeric.toString();
			} else if (distance > 0) {
				for (int i = 0; i < distance; i++) {
					strNumeric.append("0");
				}
				return strNumeric.toString();
			} else {
				return strNumeric.substring(0, currLen + distance);
			}
		}
	}

	/**
	 * 按照指定长度，将int类型的数字转换成字符串
	 *
	 * @param intNumeric
	 *            待转换的int类型数字
	 * @param formatLength
	 *            指定的长度
	 * @return 转换结果
	 */
	public static String int2String4Standard(int intNumeric, int formatLength) {
		return StringUtil.numeric4LenStan(String.valueOf(intNumeric), formatLength);
	}

	/**
	 * 按照指定长度，标准化数字
	 *
	 * @param numeric
	 *            待标准化的数字
	 * @param formatLength
	 *            指定的长度
	 * @return 转换结果
	 */
	public static String numeric4LenStan(String numeric, int formatLength) {
		StringBuilder strNumeric = new StringBuilder(numeric);
		int length = strNumeric.length();
		int distance = formatLength - length;
		if (distance == 0) {
			return strNumeric.toString();
		} else if (distance > 0) {
			strNumeric.delete(0, length);
			for (int i = 0; i < distance; i++) {
				strNumeric.append("0");
			}
			strNumeric.append(numeric);
			return strNumeric.toString();
		} else {
			return strNumeric.substring(-distance);
		}
	}

	public static String md5(String src) throws Exception {
		return StringUtil.md5(true, src);
	}

	/**
	 * 生成给定字符串的MD5串
	 *
	 * @param src
	 *            给定字符串
	 * @return 给定字符串的MD5串
	 * @throws Exception
	 */
	public static String md5(boolean mode, String src) throws Exception {
		return StringUtil.byte2HexString(mode, MessageDigest.getInstance("MD5").digest(
				src.getBytes("UTF-8")));
	}

	/**
	 * 将字节数组转换成十六进制字符串
	 *
	 * @param bytes
	 *            字节数组
	 * @return 十六进制字符串
	 */
	private static String byte2HexString(boolean mode, byte[] bytes) {
		StringBuilder hexString = new StringBuilder();
		int length = bytes.length;
		String hexByte = null;
		for (int i = 0; i < length; i++) {
			hexByte = Integer.toHexString(bytes[i] & 0xFF);
			if (hexByte.length() == 1) {
				hexString.append("0");
			}
			hexString.append(mode ? hexByte.toLowerCase() : hexByte.toUpperCase());
		}
		return hexString.toString();
	}

	/**
	 * 解析unicode编码的字符串
	 *
	 * @param unicodeStr
	 *            待解析的unicode编码字符串
	 * @return 解析后的字符串
	 */
	public static String parseUnicode(String unicodeStr) {
		StringBuilder str = new StringBuilder();
		int length = unicodeStr.length();
		int i = -1;
		int pos = 0;
		while ((i = unicodeStr.indexOf(StringUtil.U, pos)) != -1) {
			str.append(unicodeStr.substring(pos, i));
			if (i + 5 < length) {
				pos = i + 6;
				str.append((char) Integer.parseInt(
						unicodeStr.substring(i + 2, pos), 16));
			}
		}
		if (pos < length) {
			str.append(unicodeStr.substring(pos));
		}
		return str.toString();
	}

	public static List<String> commonSubsequence(char[] src, char[] dest) {
		int i = 0;
		int srcLength = src.length;
		int destLength = dest.length;
		int[] tempVector = null;
		int[] lastVector = new int[destLength + 1];
		int[] currVector = new int[destLength + 1];
		Map<Integer, List<int[]>> sameIndexMap = new HashMap<Integer, List<int[]>>(StringUtil.HASHMAP_INIT_SIZE);
		while (i < srcLength) {
			int j = 1;
			char c = src[i];
			while (j <= destLength) {
				int k = j - 1;
				if (dest[k] != c) {
					currVector[j] = Math.max(currVector[k], lastVector[j]);
				} else {
					int origNum = lastVector[k] + 1;
					currVector[j] = origNum;
					Integer num = Integer.valueOf(origNum);
					List<int[]> currSameIndexes = sameIndexMap.get(num);
					if (currSameIndexes == null) {
						currSameIndexes = new ArrayList<int[]>();
						sameIndexMap.put(num, currSameIndexes);
					}
					currSameIndexes.add(new int[] { i, k });
				}
				++j;
			}
			++i;
			tempVector = lastVector;
			lastVector = currVector;
			currVector = tempVector;
		}
		tempVector = null;
		currVector = null;
		int finalLength = lastVector[destLength];
		lastVector = null;
		List<String> subsequences = new ArrayList<String>();
		if (finalLength >= 1) {
			i = 0;
			int j = finalLength;
			List<int[]> currSameIndexes = sameIndexMap.get(Integer.valueOf(j--));
			int size = currSameIndexes.size();
			while (i < size) {
				int[] sameIndex = currSameIndexes.get(i++);
				subsequences.addAll(StringUtil.collectSubsequence(src, Integer.valueOf(j), sameIndexMap, sameIndex,
						StringUtil.appendSubsequences(src[sameIndex[0]], new ArrayList<String>())));
			}
		}
		return subsequences;
	}

	private static List<String> appendSubsequences(char character, List<String> lastSubsequences) {
		List<String> subsequences = null;
		int size = lastSubsequences.size();
		StringBuilder subsequence = new StringBuilder();
		subsequence.append(character);
		if (size >= 1) {
			int i = 0;
			int baseLength = subsequence.length();
			subsequences = new ArrayList<String>();
			while (i < size) {
				subsequences.add(subsequence.append(lastSubsequences.get(i++)).toString());
				subsequence.delete(baseLength, subsequence.length());
			}
		} else {
			subsequences = lastSubsequences;
			subsequences.add(subsequence.toString());
		}
		return subsequences;
	}

	private static List<String> collectSubsequence(char[] src, Integer length,
			Map<Integer, List<int[]>> sameIndexMap, int[] lastSameIndex, List<String> lastSubsequences) {
		int origLength = length.intValue();
		if (origLength >= 1) {
			List<String> subsequences = new ArrayList<String>();
			int i = 0;
			List<int[]> sameIndexes = sameIndexMap.get(length);
			int size = sameIndexes.size();
			while (i < size) {
				int[] sameIndex = sameIndexes.get(i++);
				if (sameIndex[0] < lastSameIndex[0] && sameIndex[1] < lastSameIndex[1]) {
					subsequences.addAll(StringUtil.collectSubsequence(src, Integer.valueOf(origLength - 1), sameIndexMap,
							sameIndex, StringUtil.appendSubsequences(src[sameIndex[0]], lastSubsequences)));
				}
			}
			return subsequences;
		} else {
			return lastSubsequences;
		}
	}

	public static List<String> commonSubstring(char[] src, char[] dest) {
		int i = 0;
		int subLength = 0;
		int srcLength = src.length;
		int destLength = dest.length;
		int[] vector = new int[destLength + 1];
		List<Integer> indexes = new ArrayList<Integer>();
		while (i < srcLength) {
			char c = src[i];
			int j = destLength;
			while (j >= 1) {
				if (dest[--j] == c) {
					int currSubLength = vector[j] + 1;
					vector[j + 1] = currSubLength;
					if (subLength < currSubLength) {
						subLength = currSubLength;
						if (indexes.size() >= 1) {
							indexes.clear();
						}
						indexes.add(Integer.valueOf(i));
					} else if (subLength == currSubLength) {
						indexes.add(Integer.valueOf(i));
					}
				} else if (vector[j + 1] != 0) {
					vector[j + 1] = 0;
				}
			}
			++i;
		}
		vector = null;
		i = 0;
		int sum = indexes.size();
		List<String> substrings = new ArrayList<String>();
		while (i < sum) {
			int index = indexes.get(i++).intValue();
			StringBuilder substring = new StringBuilder();
			substring.append(src[index--]);
			int j = 1;
			while (j++ < subLength) {
				substring.insert(0, src[index--]);
			}
			substrings.add(substring.toString());
		}
		return substrings;
	}

	public static List<String> commonSubsequence(String[] src, String[] dest) {
		int i = 0;
		int srcLength = src.length;
		int destLength = dest.length;
		int[] tempVector = null;
		int[] lastVector = new int[destLength + 1];
		int[] currVector = new int[destLength + 1];
		Map<Integer, List<int[]>> sameIndexMap = new HashMap<Integer, List<int[]>>(StringUtil.HASHMAP_INIT_SIZE);
		while (i < srcLength) {
			int j = 1;
			String term = src[i];
			while (j <= destLength) {
				int k = j - 1;
				if (!dest[k].equals(term)) {
					currVector[j] = Math.max(currVector[k], lastVector[j]);
				} else {
					int origNum = lastVector[k] + 1;
					currVector[j] = origNum;
					Integer num = Integer.valueOf(origNum);
					List<int[]> currSameIndexes = sameIndexMap.get(num);
					if (currSameIndexes == null) {
						currSameIndexes = new ArrayList<int[]>();
						sameIndexMap.put(num, currSameIndexes);
					}
					currSameIndexes.add(new int[] { i, k });
				}
				++j;
			}
			++i;
			tempVector = lastVector;
			lastVector = currVector;
			currVector = tempVector;
		}
		tempVector = null;
		currVector = null;
		int finalLength = lastVector[destLength];
		lastVector = null;
		List<String> subsequences = new ArrayList<String>();
		if (finalLength >= 1) {
			i = 0;
			int j = finalLength;
			List<int[]> currSameIndexes = sameIndexMap.get(Integer.valueOf(j--));
			int size = currSameIndexes.size();
			while (i < size) {
				int[] sameIndex = currSameIndexes.get(i++);
				subsequences.addAll(StringUtil.collectSubsequence(src, Integer.valueOf(j), sameIndexMap, sameIndex,
						StringUtil.appendSubsequences(src[sameIndex[0]], new ArrayList<String>())));
			}
		}
		return subsequences;
	}

	private static List<String> collectSubsequence(String[] src, Integer length,
			Map<Integer, List<int[]>> sameIndexMap, int[] lastSameIndex, List<String> lastSubsequences) {
		int origLength = length.intValue();
		if (origLength >= 1) {
			List<String> subsequences = new ArrayList<String>();
			int i = 0;
			List<int[]> sameIndexes = sameIndexMap.get(length);
			int size = sameIndexes.size();
			while (i < size) {
				int[] sameIndex = sameIndexes.get(i++);
				if (sameIndex[0] < lastSameIndex[0] && sameIndex[1] < lastSameIndex[1]) {
					subsequences.addAll(StringUtil.collectSubsequence(src, Integer.valueOf(origLength - 1), sameIndexMap,
							sameIndex, StringUtil.appendSubsequences(src[sameIndex[0]], lastSubsequences)));
				}
			}
			return subsequences;
		} else {
			return lastSubsequences;
		}
	}

	private static List<String> appendSubsequences(String term, List<String> lastSubsequences) {
		List<String> subsequences = null;
		int size = lastSubsequences.size();
		StringBuilder subsequence = new StringBuilder(term);
		if (size >= 1) {
			int i = 0;
			int baseLength = subsequence.length();
			subsequences = new ArrayList<String>();
			while (i < size) {
				subsequences.add(subsequence.append(lastSubsequences.get(i++)).toString());
				subsequence.delete(baseLength, subsequence.length());
			}
		} else {
			subsequences = lastSubsequences;
			subsequences.add(subsequence.toString());
		}
		return subsequences;
	}

	public static List<String> commonSubstring(String[] src, String[] dest) {
		int i = 0;
		int subLength = 0;
		int srcLength = src.length;
		int destLength = dest.length;
		int[] vector = new int[destLength + 1];
		List<Integer> indexes = new ArrayList<Integer>();
		while (i < srcLength) {
			String term = src[i];
			int j = destLength;
			while (j >= 1) {
				if (dest[--j].equalsIgnoreCase(term)) {
					int currSubLength = vector[j] + 1;
					vector[j + 1] = currSubLength;
					if (subLength < currSubLength) {
						subLength = currSubLength;
						if (indexes.size() >= 1) {
							indexes.clear();
						}
						indexes.add(Integer.valueOf(i));
					} else if (subLength == currSubLength) {
						indexes.add(Integer.valueOf(i));
					}
				} else if (vector[j + 1] != 0) {
					vector[j + 1] = 0;
				}
			}
			++i;
		}
		vector = null;
		i = 0;
		int sum = indexes.size();
		List<String> substrings = new ArrayList<String>();
		while (i < sum) {
			int index = indexes.get(i++).intValue();
			StringBuilder substring = new StringBuilder();
			substring.append(src[index--]);
			int j = 1;
			while (j++ < subLength) {
				substring.insert(0, src[index--]);
			}
			substrings.add(substring.toString());
		}
		return substrings;
	}

	public static int length(String text) {
		if (StringUtil.isEmpty(text)) {
			return 0;
		}
		text = text.trim();
		if (StringUtil.isEmpty(text)) {
			return 0;
		}
		int length = text.length();
		int size = length;
		int max = (Byte.MAX_VALUE * 2) + 1;
		for (int i = 0; i < size; i++) {
			if (text.charAt(i) > max) {
				++length;
			}
		}
		return length;
	}

    public static void main(String[] args) {
    	long s = System.currentTimeMillis();
    	List<String[]> result = StringUtil.combination(new String[] { "江苏省", "无锡市", "梁", "溪", "区", "沁", "园", "新村", "清", "名", "路", "沁", "园", "新村", "街" }, 7, 256);
    	System.out.println(System.currentTimeMillis() - s);
    	if (result != null) {
    		int i = 0;
    		int size = result.size();
    		while (i < size) {
    			System.out.println(Arrays.asList(result.get(i++)));
    		}
    		System.out.println(size);
    	}
	}
}
